package q215_quickSort;

import java.util.PriorityQueue;

public class Solution_2 {
    /*
    Java自带一个堆
     */
    public int findKth(int[] a, int n, int K){
        // 暂存K个较大的值，优先队列默认是自然排序（升序），队头元素（根）是堆内的最小元素，也就是小根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(K);
        // 遍历每一个元素，调整小根堆
        for (int num : a) {
            // 对于小根堆来说，只要没满就可以加入（不需要比较）；如果满了，才判断是否需要替换第一个元素
            if (queue.size() < K) {
                queue.offer(num);
            } else {
                // 在小根堆内，存储着K个较大的元素，根是这K个中最小的，如果出现比根还要大的元素，说明可以替换根
                if (num > queue.peek()) {
                    queue.poll(); // 高个中挑矮个，矮个淘汰
                    queue.offer(num);
                }
            }
        }
        return queue.isEmpty() ? 0 : queue.peek();
    }
}
